﻿#define _CRT_SECURE_NO_WARNINGS 1

/*
给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目 。
输入：n = 3, edges = [[0,1],[0,2],[1,2]]
输出：0
解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。
*/


#include<stdio.h>
typedef struct {
    int flag;
    int size;
}info;
typedef struct {
    int key;
    int size;
    UT_hash_handle hh;
}mergedNode;
int getflag(info* node, int idx) {
    if (node[idx].flag != idx) {
        node[idx].flag = getflag(node, node[idx].flag);
    }
    return node[idx].flag;
}
void merge(int x, int y, info* node, mergedNode** hash) {
    int fx = getflag(node, x);
    int fy = getflag(node, y);
    if (fx == fy) { return; }
    node[fy].flag = fx;
    node[fx].size += node[fy].size;
    mergedNode* hx = NULL, * hy = NULL;
    HASH_FIND_INT(*hash, &fx, hx);
    if (hx) {
        hx->size = node[fx].size;
    }
    else {
        hx = (mergedNode*)calloc(1, sizeof(mergedNode));
        hx->key = fx;
        hx->size = node[fx].size;
        HASH_ADD_INT(*hash, key, hx);
    }
    HASH_FIND_INT(*hash, &fy, hy);
    if (hy) {
        HASH_DEL(*hash, hy);
    }
}
void printhash(mergedNode* hash) {
    for (; hash; hash = hash->hh.next) {
        printf("key, %d, size, %d\n", hash->key, hash->size);
    }
}
long long countPairs(int n, int** edges, int edgesSize, int* edgesColSize) {
    info node[n];
    for (int i = 0; i < n; i++) {
        node[i].flag = i;
        node[i].size = 1;
    }
    mergedNode* hash = NULL;
    for (int i = 0; i < edgesSize; i++) {
        merge(edges[i][0], edges[i][1], node, &hash);
    }
    long long ans = (long long)n * (n - 1) / 2;
    // printhash(hash);
    for (; hash; hash = hash->hh.next) {
        ans -= (long long)hash->size * (hash->size - 1) / 2;
    }
    return ans;
}
